package util;

import server.data.Circuit;
import java.util.*;
import server.data.Link;

/**
 * Provides some useful algorithms for working with graphs. 
 * @author Danon
 */
public abstract class Algo {

    /**
     * Dijkstra's algorithm implementation.
     * Looks for the shortest path between two vertices in specified graph.
     * Uses default comparator <code>Comparator<Pair<Double, Router>></code>.
     * @param <T> type of Link bandwidth
     * @param <Router> type of vertices
     * @param g Graph to work with
     * @param v1 Source vertex
     * @param v2 Destination vertex
     * @return Length of the shortest path between v1 and v2. 
     *         If there is no path, <code>Double.MAX_VALUE</code> is returned.
     *         If there no such vertices in the graph, <code>null</code> is returned.
     */
    public static <T extends Number, Router> Double Dijkstra(DirectedGraph<Router, Link<T>> g,
            Router v1,
            Router v2) {
        if(!g.getVertices().contains(v1) || !g.getVertices().contains(v2))
            return null;
        int N = g.getVertices().size();

        // create data structures
        Circuit<Router, Link<T>> circuit = new Circuit<Router, Link<T>>(-1, "Dijkstra");
        Set<Pair<Double, Router>> q = new TreeSet<Pair<Double, Router>>(new Comparator<Pair<Double, Router>>() {

            @Override
            public int compare(Pair<Double, Router> o1, Pair<Double, Router> o2) {
                int r = o1.getA().compareTo(o2.getA());
                if(r!=0) return r;
                else return o1.getB().toString().compareTo(o2.getB().toString());
            }
        });
        Map<Router, Pair<Router, Link>> p = new HashMap<Router, Pair<Router, Link>>(N);
        Map<Router, Double> d = new HashMap<Router, Double>(N);

        // initialize
        for (Router r : g.getVertices()) {
            d.put(r, Double.MAX_VALUE);
        }
        d.put(v1, .0);
        p.put(v1, null);
        q.add(new Pair<Double, Router>(.0, v1));

        // Get the ball rolling!!!
        while (!q.isEmpty()) {
            Pair<Double, Router> pair = q.iterator().next();
            q.remove(pair);
            Double dv = pair.getA();
            Router v = pair.getB();
            if(!g.getIncidentVertices(v).isEmpty()) {
                Iterator<Pair<Router, Link<T>>> iter = g.getIncidentVertices(v).iterator();
                while(iter.hasNext()) {
                    Pair<Router, Link<T>> o = iter.next();
                    Double l = o.getB().getBandwidth().doubleValue();
                    Router w = o .getA();
                    if(d.get(w) > dv + l) {
                        if(d.get(w)!=Double.MAX_VALUE)
                            q.remove(new Pair<Double, Router>(d.get(w), w));
                        d.put(w, d.get(v)+l);
                        q.add(new Pair<Double, Router>(d.get(w), w));
                        p.put(w, new Pair<Router, Link>(v, o.getB()));
                    }
                }
            }
        }

        // Perform counter motion (reverse)
        Router r = v2;
        while(r!=null && !r.equals(v1)) {
            System.out.println(r);
            if(p.get(r)!=null) {
                circuit.addEdge(r, p.get(r).getA(), p.get(r).getB());
                r = p.get(r).getA();
            } else r = null;
        }
        if(r!=null)
            System.out.println(r);
        
        return d.get(v2);

        //TODO Implement circuit
        //return circuit;
    }
    
    /**
     * Dijkstra's algorithm implementation.
     * Looks for the shortest path between two vertices in specified graph.
     * Uses specified comparator <code>Comparator<Pair<Double, Router>></code>.
     * @param <T> type of Link bandwidth
     * @param <Router> type of vertices
     * @param g Graph to work with
     * @param v1 Source vertex
     * @param v2 Destination vertex
     * @param comparator Comparator that is used to compare pairs <code>Pair<Double, Router></code>
     * @return Length of the shortest path between v1 and v2. 
     *         If there is no path, <code>Double.MAX_VALUE</code> is returned.
     *         If there no such vertices in the graph, <code>null</code> is returned.
     */
    public static <T extends Number, Router> Circuit<Router, Link<T>> 
            Dijkstra(DirectedGraph<Router, Link<T>> g,
                     Router v1,
                     Router v2,
                     Comparator<Pair<Double, Router>> comparator) 
    {
        if(!g.getVertices().contains(v1) || !g.getVertices().contains(v2))
            return null;
        int N = g.getVertices().size();

        // create data structures
        Circuit<Router, Link<T>> circuit = new Circuit<Router, Link<T>>(-1, "Dijkstra");
        Set<Pair<Double, Router>> q = new TreeSet<Pair<Double, Router>>(comparator);
        Map<Router, Pair<Router, Link>> p = new HashMap<Router, Pair<Router, Link>>(N);
        Map<Router, Double> d = new HashMap<Router, Double>(N);

        // initialize
        for (Router r : g.getVertices()) {
            d.put(r, Double.MAX_VALUE);
        }
        d.put(v1, .0);
        p.put(v1, null);
        q.add(new Pair<Double, Router>(.0, v1));

        // Get the ball rolling!!!
        while (!q.isEmpty()) {
            Pair<Double, Router> pair = q.iterator().next();
            q.remove(pair);
            Double dv = pair.getA();
            Router v = pair.getB();
            if(!g.getIncidentVertices(v).isEmpty()) {
                Iterator<Pair<Router, Link<T>>> iter = g.getIncidentVertices(v).iterator();
                while(iter.hasNext()) {
                    Pair<Router, Link<T>> o = iter.next();
                    Double l = o.getB().getBandwidth().doubleValue();
                    Router w = o .getA();
                    if(d.get(w) > dv + l) {
                        if(d.get(w)!=Double.MAX_VALUE)
                            q.remove(new Pair<Double, Router>(d.get(w), w));
                        d.put(w, d.get(v)+l);
                        q.add(new Pair<Double, Router>(d.get(w), w));
                        p.put(w, new Pair<Router, Link>(v, o.getB()));
                    }
                }
            }
        }

        // Perform counter motion (reverse)
        Router r = v2;
        while(r!=null && !r.equals(v1)) {
            System.out.println(r);
            if(p.get(r)!=null) {
                circuit.addEdge(r, p.get(r).getA(), p.get(r).getB());
                r = p.get(r).getA();
            } else r = null;
        }
        if(r!=null)
            System.out.println(r);
        
        return circuit;
    }
}
